package 实现数据结构.算法;

/**
 * 面试题：
 *
 * @DESC https://leetcode-cn.com/problemset/algorithms/
 * @Author tzq
 * @Date 2019-08-17 17:56
 * <p>
 * 输入: ["flower","flow","flight"]
 * 输出: "fl"
 **/
public class _14_最长公共前缀 {
    public static void main(String[] args) {
        String[] strs = new String[]{"abc", "abba", "abccd"};
        String s = longestCommonPrefix(strs);
        System.out.println(s);

        String s1 = "abc";
        String s2 = "abb";
    }

    /**
     * 1.水平扫描方法
     * <p>
     * 官方：https://leetcode-cn.com/problems/longest-common-prefix/solution/zui-chang-gong-gong-qian-zhui-by-leetcode/
     * <p>
     * 时间复杂度：O(S)
     * 空间复杂度：O(1)
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(prefix) != 0) {
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) return "";
            }
        }

        return prefix;
    }


    public String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }

    //分治法
    public String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        return longestCommonPrefix(strs, 0, strs.length - 1);
    }

    private String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        } else {
            int mid = (l + r) / 2;
            String lcpLeft = longestCommonPrefix(strs, l, mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1, r);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    String commonPrefix(String left, String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if (left.charAt(i) != right.charAt(i))
                return left.substring(0, i);
        }
        return left.substring(0, min);
    }


    //二分搜索法
    public String longestCommonPrefix4(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";
        int minLen = Integer.MAX_VALUE;
        for (String str : strs)
            minLen = Math.min(minLen, str.length());
        int low = 1;
        int high = minLen;
        while (low <= high) {
            int middle = (low + high) / 2;
            if (isCommonPrefix(strs, middle))
                low = middle + 1;
            else
                high = middle - 1;
        }
        return strs[0].substring(0, (low + high) / 2);
    }

    private boolean isCommonPrefix(String[] strs, int len) {
        String str1 = strs[0].substring(0, len);
        for (int i = 1; i < strs.length; i++)
            if (!strs[i].startsWith(str1))
                return false;
        return true;
    }


    // 5.字典树的实现方式


    // 6其他很好的思路：
    //https://leetcode-cn.com/problems/longest-common-prefix/solution/14zui-chang-gong-gong-qian-zhui-zhi-xing-yong-shi-/
//            思路：
//            1. 找出minString
//            2. 排除特殊情况：
    //            1、字符串数组为空，返回 null
    //            2、字符串数组长度为1，直接返回 strs[0]
    //            3、字符串数组中存在空字符串 返回 null
//            4、数组中存在一个单词的首字母与其他单词的首字母不同，返回 null
//            3. 双层for循环找出 最长公共前缀
//            4. 注意，在内层for循环比较之前，可以再排除一种情况：如果strs[i] 与 minString 值相同，则不执行内层循环。以减少代码运行时间。



    static String mysolution(String[] strs) {
        if (strs.length == 0) return "";
        if (strs.length == 1) return strs[0];
        String min = strs[0];




        return "";
    }



    static String longestCommonPrefix5(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        if (strs.length == 1) {
            return strs[0];
        }
        String min = strs[0];
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].isEmpty()) {
                return "";
            }
            if (strs[0].charAt(0) != strs[i].charAt(0)) {
                return "";
            }
            if (strs[i].length() <= min.length()) {
                min = strs[i];
            }
        }
        for (int i = 0; i < strs.length; i++) {
            if (min.equals(strs[i])) {
                continue;
            }
            for (int j = min.length() - 1; j > 0; j--) {
                if (min.charAt(j) != strs[i].charAt(j)) {
                    min = min.substring(0, j);
                }
            }
        }
        return min;
    }


}

